package com.study.leetcode;


//https://leetcode-cn.com/problems/word-search/
public class WordSearch {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                //对每一个位置进行搜索
                if (searchWord(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean searchWord(char[][] board, int x, int y, String word, int position) {
        //已经搜索到了字符结尾则匹配到了字符串
        if (position >= word.length()) return true;
        //越界或者与当前字符不相等就是不匹配的
        if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] == word.charAt(position)) {
            //当前字符匹配正确 进行 上下左右的搜索
            //这里其实是对已经搜索过的位置经行了处理
            //处理要保证这个字符一定不可以是word中的字符
            //也就是这个字符不是英文字符
            board[x][y] += 128;
            boolean res = searchWord(board, x - 1, y, word, position + 1) || searchWord(board, x + 1, y, word, position + 1)
                    || searchWord(board, x, y - 1, word, position + 1) || searchWord(board, x, y + 1, word, position + 1);
            board[x][y] -= 128;
            return res;
        }
        return false;
    }
}
